package cn.arnold.sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {13, 17, 11, 23, 26, 72, 89, 45};
        //int[] array = {13, 11, 17, 23, 45};
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * @param array 待排序数组
     * @param left  区间的最左边
     * @param right 区间的最右边
     */
    public static void sort(int[] array, int left, int right) {
        //如果区间不只一个数
        if (left < right) {
            int pivot = array[left];     // 将区间的第一个数作为基准
            int i = left;               // 从左往右进行查找的索引，指向当前区间的最左边
            int j = right;              // 从右往左进行查找的索引，指向当前区间的最右边
            // 遍历对区间按照基准排序
            while (i < j) {
                // (一)、从右向左查找
                // 当右边的数大于基准数时，略过，继续向左查找：array[j]>pivot
                while (i < j && array[j] > pivot) {
                    j--;
                }
                // 跳出循环时，此时的j对应的元素是小于基准元素的，将j对应的元素填充到此时i对应的位置
                array[i] = array[j];
                // (二)、从左向右查找
                // 当左边的数小于基准数时，略过，继续向右查找：array[i]<pivot
                while (i < j && array[i] < pivot) {
                    i++;
                }
                // 跳出循环时，此时的i对应的元素是大于基准元素的，将i对应的元素填充到此时j对应的位置
                array[j] = array[i];
            }
            // 跳出循环时：i=j，此时再将基准元素插入到i和j重合的位置上
            array[i] = pivot;
            System.out.println("n:"+Arrays.toString(array));
            // 对基准左边元素递归分区排序
            sort(array, left, right - 1);
            // 对基准右边元素递归分区排序
            sort(array, left + 1, right);

        } else {
            return;
        }

    }
}
